import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    private int index = 0;

    public int find(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++)
            if (arr[i] == target)
                return i;
        return -1;
    }

    public TreeNode dfs(int l, int r, int[] pre ,int[] vin) {
        if (l == r)
            return null;
        
        TreeNode node = new TreeNode(pre[index]);
        int mid = find(vin, pre[index++]);
        System.out.printf("%d, %d, %d\n", l, r, vin[mid]);
        node.left = dfs(l, mid, pre, vin);
        node.right = dfs(mid + 1, r, pre, vin);
        return node;
    }

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int len = pre.length;
        
        if (len == 0)
            return null;

        TreeNode root = new TreeNode(pre[index++]);
        int mid = find(vin, pre[0]);
        root.left = dfs(0, mid, pre, vin);
        root.right = dfs(mid + 1, len, pre, vin);

        return root;
    }
}